package 左哥算法.ch06二叉树.树形dp;

import org.junit.Test;
import 左哥算法.ch06二叉树.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * 树形dp类型问题：根节点需要向子树获取信息
 */
public class Ch06树型dp {

    @Test
    public void test01(){
        TreeNode root=new TreeNode(-1);
        root.left=new TreeNode(8);
        root.left.right=new TreeNode(-9);

        root.right=new TreeNode(2);
        root.right.left=new TreeNode(0);
        root.right.left.left=new TreeNode(-3);
        root.right.left.left.right=new TreeNode(-9);
        root.right.left.left.right.right=new TreeNode(2);

//        TreeNode root = TreeNode.newLevelTree(new Integer[]{-1,8,2,null,-9,0,null,null,null,-3,null,null,-9,null,2});
        System.out.println(maxPathSum(root));
    }

    /**
     * 获取最长路径问题，
     * 每个节点有一个权值，让你找出一条权值最大的路径
     * 思路：
     *      1.每个节点向子节点索要两个信息
     *          a：到子节点的最长路径
     *          b：子节点内部的最长路径
     *      2.通过用 子节点经过自身的路径（左右最长路径+自身），对比子节点内部最长路径（）。判断是否要经过自身，然后得到最长路径
     */
    public int maxPathSum(TreeNode root) {
        int[] res = maxPathAndAllMax(root);
        return res[0];
    }

    /**
     * 获取到子节点的最长路径和子节点内部最长路径
     * 返回两个数据
     *  0：该节点内部的最长路径
     *  1：到该节点的最长路径
     * @return
     */
    public int[] maxPathAndAllMax(TreeNode node){
        if (node==null){
            return new int[]{Integer.MIN_VALUE,Integer.MIN_VALUE};
        }
        int[] res=new int[2];
        int[] leftMax = maxPathAndAllMax(node.left);
        int[] rightMax = maxPathAndAllMax(node.right);
        int passCurr=node.val
                +(Math.max(leftMax[1], 0))
                +(Math.max(rightMax[1], 0));   //经过当前节点的最长距离
        int childMax=Math.max(leftMax[0],rightMax[0]);  //子节点内的最长距离
        res[0]=Math.max(passCurr,childMax);     //当前节点内部最长路径
        int maxPath = Math.max(leftMax[1], rightMax[1]);    //左右哪侧路径较长
        res[1]=node.val+
                (Math.max(maxPath, 0));   //是否走子节点
        return res;
    }
}
